package 剑指offer;

public class 剑指Offer12矩阵中的路径Leecode79单词搜索 {
    //将这些变量定义在外面作为成员属性，保证了当前对象的可见性
    boolean[][] visited;//当前位置是否被访问过
    char[] ch;//存储word的字符数组
    char[][] board;//存储二维数组
    int m ;//二维数组的长度
    int n;//二维数组的高度
    int len;//word的长度

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.ch = word.toCharArray();
        this.m = board.length;
        this.n = board[0].length;
        this.len = word.length();
        int index = 0;//word字符串的下标
        this.visited = new boolean[m][n];

        //当word的长度大于m*n，直接返回false;
        if(len > m*n) return false;

        //否则将board中的每一个数，都作为一次起点，出发判断是否可以包含word
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                //通过这个辅助方法，来判断当前位置出发，是否可以按照规则找到word这个单词
                boolean res = help(i,j,index);
                //如果返回结果为true，表示找到了，直接返回
                if(res) return res;
            }
        }
        //如果所有的循环均完成还没有找到，返回false；
        return false;
    }

    /**
     传入i,j,index，就可以判断，该二维数组是否按照规则包含word
     i : 二维数组的行
     j : 二位数组的列
     index : word的下标
     */
    public boolean help(int i,int j,int index){
        //当index走到了word 的最后一个字符，那么直接返回true
        if(index == len) return true;

        //返回false：i,j 越界，i,j走了之前走过的路，当前位置的board[i][j] != ch[index]
        if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != ch[index]){
            return false;
        }
        //来了当前位置，表示已经走过，将当前位置置为true，表示已经来过
        visited[i][j] = true;

        //当走到了任意节点，下一步可以向上下左右任何一个位置走
        boolean res = help(i+1,j,index+1) || help(i-1,j,index+1)
                || help(i,j+1,index+1) || help(i,j-1,index+1);

        //最后要进行下一次循环，又是一个新的位置作为起点，需要把当前的结果重新还原为没有走过
        visited[i][j] = false;

        //最后返回结果
        return res;
    }
}
